// ===========   File : ListStack.c =============//

/*
    用链表的数据结构来实现栈
    链表的头节点和尾节点皆可实现入栈、出栈
    从头部入栈的方法称为头插法
    该文件只能支持 入栈 出栈 访问栈顶元素 的功能，目前不具备遍历栈空间所有元素的功能
    栈的添加数据和删除数据效率很高，但是如果需要遍历栈的元素、从栈的中间插入或者删除的话效率就很低下了
    如需添加：
        1.增加一个指向栈的临时指针，用指针去遍历这个节点的数据；
        2.增加一个临时栈，将栈的数据全部取出来，然后再放进去，注意先进后出的顺序
*/

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include "ListStack.h"


/* 
    构造函数
    创建一个栈的对象
 */
LinkedListStack * NewLinkedListStack()
{   
    LinkedListStack *s = malloc(sizeof(LinkedListStack));
    s->size = 0;
    s->top = NULL;
    return s;
}


/*  
    析构函数
    s:删除该节点之后的一个节点
 */
void DelLinkedListStack(LinkedListStack *s)
{
    while(s->top)
    {
        ListNode *n=s->top->next;
        free(s->top);
        s->top=n;
    }
    free(s);
}


/* 
    获取栈的长度
    s:获取栈的高度
 */
int StackSize(LinkedListStack *s)
{
    assert(s);
    return s->size;
}

/* 
    判断栈是否为空
    s:判断栈的高度是否为空
 */
_Bool StackIsEmpty(LinkedListStack *s)
{
    assert(s);
    return StackSize(s) == 0;
}


/* 
    访问栈顶元素
    s:栈的对象
 */
int StackPeek(LinkedListStack *s)
{
    assert(s);
    assert(StackSize(s) != 0);

    return s->top->val;
}

/* 
    入栈
    s:栈的对象
    num:入栈的值
 */
void StackPush(LinkedListStack *s,int num)
{
    assert(s);
    ListNode *node = (ListNode *)malloc(sizeof(ListNode));
    node->next = s->top;
    node->val = num;
    s->top = node;
    s->size++;
}

/* 
    出栈
    s:栈的对象
    return:返回栈顶的值
 */
int StackPop(LinkedListStack *s)
{
    if(s->size == 0)
    {
        printf("stack is empty\n");
        return INT_MAX;
    }

    assert(s);
    int val = StackPeek(s);
    ListNode *temp = s->top;
    s->top = s->top->next;

    free(temp);
    s->size--;
    return val;
}

/* 打印栈的当前高度以及栈顶的值 */
void StackPrintf(LinkedListStack *s)
{   
    if(StackIsEmpty(s)) {
        printf("**** 栈为空 ****\n");
        return ;
    }
    printf("**** 栈的高度：%d ****\n",StackSize(s));
    printf("**** 栈顶的值：%d ****\n",StackPeek(s));
}


/* main 函数 */
int main(int argc, char * argv[])
{
    printf("=================   构造栈的对象  打印栈的状态   ================\n");
    LinkedListStack * Stack = NewLinkedListStack();
    StackPrintf(Stack);

    printf("=================   第一次数据入栈  打印栈的状态   ================\n");
    StackPush(Stack,100);
    StackPrintf(Stack);

    printf("=================   第二次数据入栈  打印栈的状态   ================\n");
    StackPush(Stack,200);
    StackPrintf(Stack);

    printf("=================   第三次数据入栈  打印栈的状态   ================\n");
    StackPush(Stack,500);
    StackPrintf(Stack);

    printf("=================   第一次数据出栈  打印栈的状态   ================\n");
    printf("取出栈顶的值:%d\n",StackPop(Stack));
    StackPrintf(Stack);

    printf("=================   第二次数据出栈  打印栈的状态   ================\n");
    printf("取出栈顶的值:%d\n",StackPop(Stack));
    StackPrintf(Stack);

    printf("=================   第三次数据出栈  打印栈的状态   ================\n");
    printf("取出栈顶的值:%d\n",StackPop(Stack));
    StackPrintf(Stack);

    printf("=================       删除栈         ================\n");
    DelLinkedListStack(Stack);
    
}

